| 每日“力扣”系利1 ListNode | 您所在的位置：网站首页 › python listnode › 每日“力扣”系利1 ListNode |
每日“力扣”系利1 ListNode
|
作为一个化学人，面对马上到来的期末考试，虽然复习之路漫漫，但还是看不下去了，索性刷一点leetcode，补一点基础。 由于之前很少做算法，虽然难度不大，做起来也很吃力，干脆就来记录一下。 今天看到的这道题是这样的：  题目说的很清楚，利用链表完成一个加和运算，数据源的数位是分离的。 刚看到这个题的时候，我原本的思路是这样的： 第一，把每个链表中的数字都先还原成十进制的原始数据，然后进行加和。 第二，创建一个迭代器，在链表中每个数位每个数位的加过去。 为了调试方便（ 当然不会和你说是为了蹭自动补全），两种思路我都先使用IDEA进行了尝试。 数字复原的方法： public static void main(String [] args ){ // 数据来源1 LinkedList l1 = new LinkedList(); l1.add(7); l1.add(5); l1.add(1); // 数据来源2 LinkedList l2 = new LinkedList(); l2.add(5); l2.add(2); l2.add(9); // 来俩迭代器 Iterator iterator1 = l1.iterator(); Iterator iterator2 = l2.iterator(); // 初始化存储结果的链表 LinkedList result = new LinkedList(); // 临时变量们 int sum1 = 0; int sum2 = 0; int i = 0; //用于记录当前数字的倍率 // 将来源于1的数字进行复原 while (iterator1.hasNext()){ sum1 += (Math.pow(10,i)) * (int)iterator1.next(); i++; } // 临时变量还原，再次将来源2的数字还原 i = 0; while (iterator2.hasNext()){ sum2 += (Math.pow(10,i)) * (int)iterator2.next(); i++; } // 直接加和 int sum_tem = sum1+sum2; // 结果逐位输出 int tem = 0; while (sum_tem>=1){ tem = sum_tem%10; result.add(tem); sum_tem = sum_tem /10; } System.out.println(result); }这里是结果：  位数少的时候，这样应该是可以的，但是貌似官方想到了这个问题，于是：  生硬方法失败最关键的是，看了提供的代码后注意到，这里题目使用的也不是我使用的LinkedList类：  看到这里，我是没有看懂这个ListNode类是什么意思，于是果断去选择参考官方给出的示例代码：  官方给出的解题思路伪代码public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10); // 1
curr = curr.next;
if (p != null) p = p.next; // 2
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
作者：LeetCode
链接：https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode/上面是官方给出的示例代码。 看这段代码是出现过几个问题，也在这里稍加记录： 第一，添加对null的判断的必要性： 题目只是排除了0出现可能导致的问题，没有排除数据源为空时，也就是[]时的问题，所以在进行取值时需要进行判断。 第二，next的问题： 这里在我理解来看，是类似于指针的用法，1处，将新的一位的结果保存在新的块中，之后将现在的块指向新块，之后完成指针的移动。2处则是直接将在数据源中的指向向后移动。 第三，最后返回的结果不是curr或者dummyHead，而是dummyHead.next： 我们可以看到在开始的时候，有一步将dummyHead赋值给curr，而此时dummyHead均是仅有一个结点（值为0）。 看过赋值的规则就可以知道，这里的赋值为引用赋值，故最后的curr和dummyHead，两个结点的指向是不一样的。就本题而言，curr此时指向结果的最后一位，而dummyHead仍然保留在结点0的位置，想要返回给主函数结果，自然是要将结果的第一个指向返回。 补充，看过其他人在下面的补充很评论，为了避免最后一位的加和出现10时导致的bug，对源代码的循环部分添加一个条件：  class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode p = l1;
ListNode q = l2;
ListNode iterator = result;
int flag = 0;
while(p != null | q != null | flag != 0 ){
int x = (p == null)? 0: p.val;
int y = (q == null)? 0 :q.val;
int sum = x + y + flag;
flag = sum/10;
iterator.next = new ListNode(sum%10);
iterator = iterator.next;
if(p != null) p = p.next;
if(q != null) q = q.next;
}
return result.next;
}
}这是我最后提交的代码。 另外，解决这个问题的时候，很好奇这个解法的精髓，next，是怎么实现的。 后面了解更多后再来更新。 有知道的朋友也可以在可以告知一下我吼。 |
【本文地址】